package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

public class Demo2 {

    //274. H 指数
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int mid, left = 0, right = citations.length - 1;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (citations[mid] < citations.length - mid) left = mid + 1;
            else right = mid;
        }
        return Math.min(citations[left], citations.length - left);
    }


    //275. H 指数 II
    public int hIndex2(int[] citations) {
        int mid, left = 0, right = citations.length - 1;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (citations[mid] < citations.length - mid) left = mid + 1;
            else right = mid;
        }
        return Math.min(citations[left], citations.length - left);
    }


    //38. 外观数列
    public String countAndSay(int n) {
        String ret = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder tmp = new StringBuilder();
            for (int left = 0, right = 0; right < ret.length(); ) {
                while (right < ret.length() && ret.charAt(left) == ret.charAt(right)) right++;
                tmp.append(right - left);
                tmp.append(ret.charAt(left));
                left = right;
            }
            ret = tmp.toString();
        }
        return ret;
    }


    //2558. 从数量最多的堆取走礼物
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int x : gifts) queue.add(x);

        // 取走礼物
        for (int i = 0; i < k; i++) {
            int gift = queue.poll();
            queue.add((int) Math.sqrt(gift));
        }
        long ret = 0;
        while (!queue.isEmpty()) ret += queue.poll();
        return ret;
    }


    //1419. 数青蛙
    public int minNumberOfFrogs(String croakOfFrogs) {
        int len = 5;
        int[] arr = new int[5];       // 分别记录croak每个字符出现的次数
        String flag = "croak";

        for (char ch : croakOfFrogs.toCharArray()) {
            int index = flag.indexOf(ch);
            if (ch == 'c') {
                if (arr[len - 1] > 0) arr[len - 1]--;
                arr[index]++;
            } else {
                if (arr[index - 1] > 0) {
                    arr[index - 1]--;
                    arr[index]++;
                } else {
                    return -1;
                }
            }
        }
        for (int i = 0; i < 4; i++) if (arr[i] > 0) return -1;
        return arr[len - 1];
    }


    //75. 颜色分类
    public void sortColors(int[] nums) {
        // left下标代表红色的最后一个位置，right下标代表蓝色的第一个位置
        // 红色[0,left]   白色[left+1,right-1]   蓝色[right,len-1]
        int left = -1, right = nums.length, i = 0;
        while(i < right) {
            if(nums[i] == 0) swap(nums,++left,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--right,i);
        }
    }
//    private void swap(int[] nums, int x, int y) {
//        int tmp = nums[x];
//        nums[x] = nums[y];
//        nums[y] = tmp;
//    }


    //912. 排序数组
    public int[] sortArray(int[] nums) {
        partition(nums, 0, nums.length - 1);
        return nums;
    }
    private void partition(int[] nums, int l, int r) {
        if(l >= r) return;
        // 分3块 快速排序
        // val < key:[l,left]   val == key:[left+1,right-1]   val > key[right,r]
        int left = l - 1, right = r + 1, i = l;
        // 随机选择一个key
        int key = nums[new Random().nextInt(r - l + 1) + l];

        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        // 对左区间和右区间进行快排
        partition(nums,l,left);
        partition(nums,right,r);
    }

    private void swap(int[] nums, int x, int y ) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }



    //LCR 076. 数组中的第 K 个最大元素
    // 使用分3块的快速排序
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int l, int r, int k) {
        if(l >= r) return nums[r];

        int left = l - 1, right = r + 1, i = l;
        // 1. 随机寻找一个key值
        int key = nums[new Random().nextInt(r - l + 1) + l];
        // 2. 根据key将元素排到key的前后位置
        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        // 此时val < key:[l,left]   val == key:[left+1,right-1]   val > key:[right,r]
        int c = r - right + 1, b = right - left - 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

//    private void swap(int[] nums, int x, int y ) {
//        int tmp = nums[x];
//        nums[x] = nums[y];
//        nums[y] = tmp;
//    }



    //面试题 17.14. 最小K个数
    public int[] smallestK(int[] arr, int k) {
        qsort2(arr, 0, arr.length - 1, k);
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) ret[i] = arr[i];
        return ret;
    }

    private void qsort2(int[] arr, int l, int r, int k) {
        if(l >= r) return;
        // 随机选择一个关键字
        int key = arr[new Random().nextInt(r - l + 1) + l];
        // 将数组分 3 块
        // [l, left]:val < key     [left+1,right-1]:val == key    [right, r]:val > key
        int left = l - 1, right = r + 1, i = l;
        while(i < right) {
            if(arr[i] < key) swap(arr, ++left, i++);
            else if(arr[i] == key) i++;
            else swap(arr,--right, i);
        }
        int a = left - l + 1, b = right - left - 1;
        if(a > k) qsort(arr, l, left, k);
        else if(a + b >= k) return;
        else qsort(arr, right, r, k - a - b);

    }
//    private void swap(int[] arr, int x, int y) {
//        int tmp = arr[x];
//        arr[x] = arr[y];
//        arr[y] = tmp;
//    }



    //LCR 170. 交易逆序对的总数
    int[] tmpArray;
    public int reversePairs(int[] record) {
        tmpArray = new int[record.length];
        return mergeSort(record, 0, record.length - 1);
    }

    private int mergeSort(int[] arr, int left, int right) {
        if(left >= right) return 0;

        // 1. 选择中间点，将数组划分成两个部分
        // [left,mid]   [mid+1,right]
        int mid = (left + right) / 2;
        // 计算左边部分逆序对 + 左排序 + 计算右半部分逆序对 + 右排序
        int ret = mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right);

        // 2. 计算一左一右逆序对的个数 + 左右区间排序
        int l = left, r = mid + 1, k = left;
        while(l <= mid && r <= right) {
            if(arr[l] > arr[r]) {
                tmpArray[k++] = arr[l++];
                ret += right - r + 1;
            }
            else tmpArray[k++] = arr[r++];
        }
        while(l <= mid) tmpArray[k++] = arr[l++];
        while(r <= right) tmpArray[k++] = arr[r++];

        // 3. 将排序后的tmpArray数组放回原数组arr
        while(left <= right) arr[left] = tmpArray[left++];
        return ret;
    }


    //9.12 排序数组
    //int[] tmpArray;
    public int[] sortArray2(int[] nums) {
        tmpArray = new int[nums.length];
        mergeSort2(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort2(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        // 1. 分为左，右两个区间
        mergeSort2(nums, left, mid);
        mergeSort2(nums, mid + 1, right);

        // 2. 合并数组
        int l = left, r = mid + 1, k = 0;
        while(l <= mid && r <= right) {
            if(nums[l] <= nums[r])  tmpArray[k++] = nums[l++];
            else tmpArray[k++] = nums[r++];
        }
        while(l <= mid) tmpArray[k++] = nums[l++];
        while(r <= right) tmpArray[k++] = nums[r++];

        // 3. 将tmpArray中的元素放回原数组
        for(int i = left, j = 0; i <= right; i++, j++) {
            nums[i] = tmpArray[j];
        }
    }



    //

}